package 滑动窗口;

import java.util.HashMap;
import java.util.Map;

public class 最小覆盖子串8 {
    //https://leetcode.cn/problems/minimum-window-substring/submissions/668036515/
    public static String minWindow1(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        Map<Character,Integer> hash1 = new HashMap<>();
        for (char c : t) {
            hash1.put(c, hash1.getOrDefault(c, 0) + 1);
        }
        Map<Character,Integer> hash2 = new HashMap<>();
        String ret = "";
        int min = Integer.MAX_VALUE;
        for (int left = 0, right = 0, count = 0, len = hash1.size(), n = 0; right < s.length; right++) {
            char in = s[right];
            hash2.put(in,hash2.getOrDefault(in,0) + 1);
            if (hash2.get(in).equals(hash1.get(in))) {
                count++;
            }
            while (count == len) {
                n = right - left + 1;
                String tmp = ss.substring(left,left + n);
                if (min > tmp.length()) {
                    min = tmp.length();
                    ret = tmp;
                }
                char out = s[left];
                if (hash2.get(out).equals(hash1.get(out))) {
                    count--;
                }
                hash2.put(out,hash2.get(out) - 1);
                left++;
            }
        }
        return ret;
    }
    public static String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        int[] hash1 = new int[128];
        int kinds = 0;
        for(char ch : t) {
            if (hash1[ch]++ == 0) kinds++;
        }

        int[] hash2 = new int[128];

        int minlen = Integer.MAX_VALUE, begin = -1;
        for(int left = 0, right = 0, count = 0; right < s.length; right++) {
            char in = s[right];
            if (++hash2[in] == hash1[in]) count++;
            while (kinds == count) {
                if (right - left + 1 < minlen) {
                    begin = left;
                    minlen = right - left + 1;
                }
                char out = s[left++];
                if (hash2[out]-- == hash1[out]) count--;
            }
        }
        if (begin == -1) return "";
        return ss.substring(begin,begin + minlen);
    }


    public static void main(String[] args) {
        String s = "a", t = "aa";
        minWindow(s,t);
        while (true) if (2 < 1) System.out.println("hello"); else { // 连着带
            System.out.println("yes");
            System.out.println("haha");
        }
    }
}
